import java.util.Arrays;

public class MyHeap {
    //自己进行模拟实现一个堆；
    public int[] elem;
    public int usedSize;
    public MyHeap(){
        this.elem=new int[10];
    }
    //由于堆的底层是一个顺序表，所以要进行底层数据表的实现；
    public void initElem(int[] array){
        for(int i=0;i<array.length;i++){
            this.elem[i]=array[i];
            this.usedSize++;
        }
    }
    //进行堆的创建；
    //创建一会大根堆；
    public  void createHeap(){
        for(int parent=(usedSize-1-1)/2;parent>=0;parent--){
            //进行使用向下调整的方式进行大根堆的创建；
            siftDown(parent,this.usedSize);
        }
    }
    public void siftDown(int parent,int usedSize){
        int child=2*parent+1;//默认使用做孩子进行比较；
        while(child<usedSize){
            //进行判断左右孩子的值的大小，选择值大的孩子与父亲进行比较；
            if(child+1<usedSize&&elem[child]<elem[child+1]){
                child++;
            }
            if(elem[child]>elem[parent]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }
    //向堆中插入元素；
    public void offer(int val){
        //先进行判断堆是否已经满了：
        if(isFull()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        siftUp(usedSize);
        usedSize++;
    }
    //进行判断堆是否已经满了；
    public boolean isFull(){
        return usedSize==elem.length;
    }
    //进行向上调整操作；
    public void siftUp(int child){
        int parent=(child-1)/2;
        while(parent>=0){
            if(elem[parent]<elem[child]){
                int tmp=elem[parent];
                elem[parent]=elem[child];
                elem[child]=tmp;
            }else{
                break;
            }
            child=parent;
            parent=(child-1)/2;
        }
    }

    //删除堆中的元素；若没有规定某个元素，就会删除堆顶元素；
    public void delete(){
        int val=elem[0];
        if(isEmpty()){
            return;
        }
        int tmp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=tmp;
        siftDown(0,usedSize-1);
        usedSize--;
    }
    public boolean isEmpty(){
        return usedSize==0;
    }
    //进行堆排序；
    public void heapSort() {
        int end = usedSize - 1;
        while (end > 0) {
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            siftDown(0, end);
            end--;
        }
    }
}
